package heap;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author pengfei.hpf
 * @date 2020/2/29
 * @verdion 1.0.0
 */
public class KSmallestPairs {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new LinkedList<>();
        if(nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0){
            return res;
        }
        PriorityQueue<List<Integer>> queue = new PriorityQueue<>((o1, o2) -> (o1.get(0) + o1.get(1) - o2.get(0) - o2.get(1)));
        for(int i = 0; i < nums1.length; i ++){
            for(int j = 0; j < nums2.length; j++){
                List<Integer> list = new ArrayList<>();
                list.add(nums1[i]);
                list.add(nums2[j]);
                queue.add(list);
            }
        }

        for(int i = 0; i < k && !queue.isEmpty(); i ++){
            res.add(queue.poll());
        }
        return res;
    }
}
